package de.hsfulda.et.problemloesen.ws1112.grp2.knapsack;

import java.util.ArrayList;

public class DepthFirstSearch02 implements Optimizer {

    private ArrayList<KnapsackItem> items;
    private ArrayList<Long> boundaryArrayList;
    private Long counter = 0L;

    public Knapsack optimize(ArrayList<KnapsackItem> items,
	    ArrayList<Long> boundaryArrayList) {

	this.items = items;
	this.boundaryArrayList = boundaryArrayList;
	counter = 0L;
	Knapsack ks = new Knapsack(items.size());
	ks = optimizeRecursive(0, ks);
	System.out.println("Counter: " + this.counter);
	return ks;
    }

    private Knapsack optimizeRecursive(int i, Knapsack ks) {

	this.counter++;
	if (i == items.size()) return ks;
	Knapsack ks1 = ks.clone();
	ks1 = optimizeRecursive(i + 1, ks1);
	// does item at i fit?
	if (ks.getSumWeight() + items.get(i).getWeight() <= boundaryArrayList
		.get(0)) {
	    Knapsack ks2 = ks.clone();
	    ks2.packIn(items.get(i), i);
	    ks2 = optimizeRecursive(i + 1, ks2);
	    if ((ks2.getSumWeight() - boundaryArrayList.get(0)) == 0) 
		return ks2;
	}
	return ks1;
    }
}
